package com.leetcode.algorithm.y22.m06;

import java.util.List;

/**
 * 139. 单词拆分
 * 
 * https://leetcode.cn/problems/word-break/
 * 
 * @author jie.deng
 *
 */
class Question0139Solution01 {

	public boolean wordBreak(String s, List<String> wordDict) {
		return wordBreak(s, 0, wordDict);
	}

	private boolean wordBreak(String s, int beginIdx, List<String> wordDict) {
		if (beginIdx >= s.length()) {
			return true;
		}
		String str = s.substring(beginIdx);
		for (String word : wordDict) {
			if (str.startsWith(word) && wordBreak(s, beginIdx + word.length(), wordDict)) {
				return true;
			}
		}
		return false;
	}

}